package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 310. 最小高度树
 * 深度优先遍历图, 找出最长路径
 * 深度优先遍历 记录节点离当前节点 路径深度
 *
 * @author fy
 * @date 2022/4/7 8:30
 */
public class Solution310_1 {

    private List<Integer>[] adj;
    private int v;
    private int e;

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n <= 0) {
            return res;
        }
        if (n == 1) {
            res.add(0);
            return res;
        }
        if (n == 2) {
            res.add(0);
            res.add(1);
            return res;
        }
        this.v = n;
        this.e = edges.length;

        this.initAdj(edges);

        int[] from = new int[this.v];
        Arrays.fill(from, -1);
        // 查找到0节点路径最远的节点x
        int x = this.findLongestNode(0, from);
        // 找到与节点 x 最远的节点 y
        //Arrays.fill(from, -1);
        int y = this.findLongestNode(x, from);

        // 求出节点 x 到节点 y 的路径
        List<Integer> path = new ArrayList<>();
        int parent = y;
        while (parent != -1) {
            path.add(parent);
            parent = from[parent];
        }

        // 如果是偶数个节点, 则中间节点有两个, 如果是奇数则只有一个
        int h = path.size();
        if (h % 2 == 0) {
            res.add(path.get(h / 2 - 1));
        }
        res.add(path.get(h / 2));

        return res;
    }

    private void initAdj(int[][] edges) {
        // 初始化邻接表
        adj = new List[this.v];
        for (int i = 0; i < this.v; i++) {
            adj[i] = new ArrayList<>();
        }
        // 初始化邻接表中的边
        for (int i = 0; i < this.e; i++) {
            // 边的两端是节点值
            int[] edge = edges[i];
            // 因为是无向图, 需要在两端节点都存
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
    }

    private int findLongestNode(int node, int[] from) {
        // 记录node到其他节点的路径长度, 当前是无向无权图, 默认相邻两节点间的路径长度为1
        int[] dist = new int[this.v];
        Arrays.fill(dist, -1);
        // 初始话起始节点的路径为0
        dist[node] = 0;
        // 初始化起始节点的来自节点为-1
        from[node] = -1;

        // 进行一次深度遍历
        dfs(node, from, dist);

        // 记录最长路径 0 > -1(默认值), -1 为不可达, 即不连通
        int maxDist = 0;
        // 到node 最长路径 的节点
        int longestNode = -1;
        // 依次遍历dist读取dist中最大的值则 下标为对应的节点
        for (int i = 0; i < dist.length; i++) {
            if (dist[i] > maxDist) {
                maxDist = dist[i];
                longestNode = i;
            }
        }
        return longestNode;
    }

    private void dfs(int node, int[] from, int[] dist) {
        // 依次dfs当前节点的 相邻连接节点
        for (Integer newNode : this.adj[node]) {
            // 如果当前节点没有访问过, 也就是说他的路径长度还是-1
            if (dist[newNode] <= -1) {
                // 将新遍历的节点的来自节点为当前节点
                from[newNode] = node;
                // 将距离 记录为当前节点的距离 再 + 1
                dist[newNode] = dist[node] + 1;
                // 将新节点再进行dfs
                dfs(newNode, from, dist);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = new int[][]{{0, 1}, {0, 2}, {0, 3}, {3, 4}};

        List<Integer> res = new Solution310_1().findMinHeightTrees(n, edges);

        System.out.println(res);
    }
}
